/* Copyright (c) <2003-2022> <Julio Jerez, Newton Game Dynamics>
*
* This software is provided 'as-is', without any express or implied
* warranty. In no event will the authors be held liable for any damages
* arising from the use of this software.
*
* Permission is granted to anyone to use this software for any purpose,
* including commercial applications, and to alter it and redistribute it
* freely, subject to the following restrictions:
*
* 1. The origin of this software must not be misrepresented; you must not
* claim that you wrote the original software. If you use this software
* in a product, an acknowledgment in the product documentation would be
* appreciated but is not required.
*
* 2. Altered source versions must be plainly marked as such, and must not be
* misrepresented as being the original software.
*
* 3. This notice may not be removed or altered from any source distribution.
*/

#include "ndCoreStdafx.h"
#include "ndSort.h"
#include "ndDebug.h"
#include "ndVector.h"
#include "ndMatrix.h"
#include "ndProfiler.h"
#include "ndIsoSurface.h"

// adapted from code by written by Paul Bourke may 1994
//http://paulbourke.net/geometry/polygonise/

class ndIsoSurface::ndImplementation : public ndClassAlloc
{
	public:
	class ndEdge
	{
		public:
		ndInt32 m_midPoint;
		ndInt32 m_p0;
		ndInt32 m_p1;
	};

	class ndIsoCell
	{
		public:
		ndVector m_isoValues[8];
	};

	ndImplementation();
	~ndImplementation();

	void Clear();
	ndVector GetOrigin() const;
	void BuildLowResolutionMesh(ndIsoSurface* const me, const ndArray<ndVector>& pointCloud, ndFloat32 gridSize);
	void BuildHighResolutionMesh(ndIsoSurface* const me, const ndArray<ndVector>& pointCloud, ndFloat32 gridSize, ndCalculateIsoValue* const computeIsoValue);

	ndInt32 GenerateLowResIndexList(const ndIsoSurface* const me, 
		ndInt32* const indexList, ndInt32 strideInFloats, 
		ndReal* const posit, ndReal* const normals);

	private:
	class ndGridHash
	{
		public:
		ndGridHash()
		{
		}

		ndGridHash(const ndGridHash& src, ndInt8 cellType)
		{
			m_gridCellHash = src.m_gridCellHash;
			m_cellType = ndUnsigned8(cellType);
		}

		ndGridHash(ndInt32 x, ndInt32 y, ndInt32 z)
		{
			m_gridCellHash = 0;
			m_x = ndUnsigned16(x);
			m_y = ndUnsigned16(y);
			m_z = ndUnsigned16(z);
		}

		ndGridHash(const ndVector& grid)
		{
			ndAssert(grid.m_x >= ndFloat32(0.0f));
			ndAssert(grid.m_y >= ndFloat32(0.0f));
			ndAssert(grid.m_z >= ndFloat32(0.0f));
			ndAssert(grid.m_x < ndFloat32(256.0f * 256.0f));
			ndAssert(grid.m_y < ndFloat32(256.0f * 256.0f));
			ndAssert(grid.m_z < ndFloat32(256.0f * 256.0f));
			
			ndVector hash(grid.GetInt());
			m_gridCellHash = 0;
			m_x = ndUnsigned16(hash.m_ix);
			m_y = ndUnsigned16(hash.m_iy);
			m_z = ndUnsigned16(hash.m_iz);
		}

		union
		{
			struct
			{
				ndUnsigned16 m_x;
				ndUnsigned16 m_y;
				ndUnsigned16 m_z;
				ndUnsigned8 m_cellType;
			};
			struct
			{
				ndUnsigned8 m_xLow;
				ndUnsigned8 m_xHigh;
				ndUnsigned8 m_yLow;
				ndUnsigned8 m_yHigh;
				ndUnsigned8 m_zLow;
				ndUnsigned8 m_zHigh;
			};
			ndUnsigned64 m_gridCellHash : 48;
			ndUnsigned64 m_gridFullHash;
		};
	};

	class ndGridHashSteps
	{
		public:
		ndGridHashSteps()
		{
			m_steps[0] = ndGridHash(-1, -1, -1);
			m_steps[1] = ndGridHash(0, -1, -1);
			m_steps[2] = ndGridHash(-1, 0, -1);
			m_steps[3] = ndGridHash(0, 0, -1);
			m_steps[4] = ndGridHash(-1, -1, 0);
			m_steps[5] = ndGridHash(0, -1, 0);
			m_steps[6] = ndGridHash(-1, 0, 0);
			m_steps[7] = ndGridHash(0, 0, 0);

			m_cellType[0] = 5;
			m_cellType[1] = 6;
			m_cellType[2] = 1;
			m_cellType[3] = 2;
			m_cellType[4] = 4;
			m_cellType[5] = 7;
			m_cellType[6] = 0;
			m_cellType[7] = 3;
		}

		ndGridHash m_steps[8];
		ndUnsigned8 m_cellType[8];
	};
	
	class ndUpperDigit
	{
		public:
		ndUpperDigit()
			:m_x(0)
			,m_y(0)
			,m_z(0)
		{
		}
		ndInt32 m_x;
		ndInt32 m_y;
		ndInt32 m_z;
	};

	void CreateGrids();
	void ClearBuffers();
	void SortCellBuckects();
	void GenerateLowResIsoSurface();
	void ProcessLowResCell(ndIsoCell& cell);
	void MakeTriangleList(ndIsoSurface* const me);
	void CalculateNormals(ndIsoSurface* const me);
	
	void GenerateHighResIndexList(ndIsoSurface* const me);
	void RemoveDuplicates(const ndArray<ndVector>& points);
	void CalculateAabb(const ndArray<ndVector>& points, ndFloat32 gridSize);
	void GenerateHighResIsoSurface(ndCalculateIsoValue* const computeIsoValue);
	void ProcessHighResCell(ndIsoCell& cell, ndCalculateIsoValue* const computeIsoValue);
	ndVector InterpolateLowResVertex(const ndVector& p1, const ndVector& p2) const;
	ndVector InterpolateHighResVertex(ndFloat32 isolevel, const ndVector& p1, const ndVector& p2) const;

	ndVector m_boxP0;
	ndVector m_boxP1;
	ndVector m_gridSize;
	ndVector m_invGridSize;
	ndArray<ndGridHash> m_hashGridMap;
	ndArray<ndGridHash> m_hashGridMapScratchBuffer;
	ndArray<ndVector> m_triangles;
	ndArray<ndVector> m_trianglesScratchBuffer;

	ndFloat32 m_isoValue;
	ndInt32 m_volumeSizeX;
	ndInt32 m_volumeSizeY;
	ndInt32 m_volumeSizeZ;
	ndUpperDigit m_upperDigitsIsValid;
	
	static ndEdge m_edges[];
	static ndInt32 m_faces[][3];
	static ndInt32 m_edgeScan[];
	static ndInt32 m_facesScan[];
	static ndVector m_gridCorners[];

	friend class ndIsoSurface;
};

ndInt32 ndIsoSurface::ndImplementation::m_facesScan[] = { 0,0,1,2,4,5,7,9,12,13,15,17,20,22,25,28,30,31,33,35,38,40,43,46,50,52,55,58,62,65,69,73,76,77,79,81,84,86,89,92,96,98,101,104,108,111,115,119,122,124,127,130,132,135,139,143,146,149,153,157,160,164,169,174,176,177,179,181,184,186,189,192,196,198,201,204,208,211,215,219,222,224,227,230,234,237,241,245,250,253,257,261,266,270,275,280,284,286,289,292,296,299,303,305,308,311,315,319,324,328,333,336,338,341,345,349,352,356,361,364,366,370,375,380,384,389,391,395,396,397,399,401,404,406,409,412,416,418,421,424,428,431,435,439,442,444,447,450,454,457,461,465,470,473,475,479,482,486,489,494,496,498,501,504,508,511,515,519,524,527,531,535,540,544,549,554,558,561,565,569,572,576,581,586,590,594,597,602,604,609,613,615,616,618,621,624,628,631,635,639,644,647,651,655,660,662,665,668,670,673,677,681,686,690,695,700,702,706,709,714,718,721,723,727,728,731,735,739,744,748,753,756,760,764,769,774,776,779,783,785,786,788,791,794,796,799,803,805,806,809,811,815,816,818,819,820};
ndInt32 ndIsoSurface::ndImplementation::m_edgeScan[] = { 0,0,3,6,10,13,19,23,28,31,35,41,46,50,55,60,64,67,71,77,82,88,95,102,108,114,119,128,134,141,147,155,160,163,169,173,178,184,193,198,204,210,217,224,230,237,245,251,256,260,265,270,274,281,289,295,300,307,313,321,326,334,341,348,352,355,361,367,374,378,385,390,396,402,409,418,426,431,437,443,448,454,461,470,478,485,493,501,508,517,525,537,546,554,561,570,576,580,587,592,598,603,611,615,620,627,635,643,650,656,663,668,672,677,683,689,694,700,707,712,716,724,731,740,746,753,759,765,768,771,777,783,790,796,805,812,820,824,829,836,842,847,853,859,864,868,873,880,886,893,901,909,916,921,925,933,938,944,949,956,960,966,975,982,990,999,1011,1019,1028,1035,1043,1051,1058,1066,1075,1082,1088,1093,1099,1105,1110,1118,1127,1134,1140,1146,1151,1158,1162,1169,1175,1181,1184,1188,1195,1202,1210,1215,1223,1229,1236,1241,1247,1255,1262,1266,1271,1276,1280,1285,1291,1299,1306,1312,1319,1326,1332,1338,1343,1352,1358,1363,1367,1373,1376,1381,1389,1395,1402,1408,1417,1422,1428,1434,1441,1448,1454,1459,1465,1469,1472,1476,1481,1486,1490,1495,1501,1505,1508,1513,1517,1523,1526,1530,1533,1536 };

ndIsoSurface::ndImplementation::ndEdge ndIsoSurface::ndImplementation::m_edges[] =
{
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 8, 0, 4 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 9, 1, 5 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 10, 2, 6 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 11, 3, 7 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 11, 3, 7 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 4, 4, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 5, 6, 5 },
	{ 6, 7, 6 },
	{ 10, 2, 6 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 5, 6, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 4, 4, 5 },
	{ 5, 6, 5 },
	{ 9, 1, 5 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 4, 4, 5 },
	{ 7, 7, 4 },
	{ 8, 0, 4 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 10, 2, 6 },
	{ 11, 3, 7 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 9, 1, 5 },
	{ 11, 3, 7 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 8, 0, 4 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 11, 3, 7 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 2, 2, 3 },
	{ 9, 1, 5 },
	{ 10, 2, 6 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 3, 3, 0 },
	{ 8, 0, 4 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 2, 2, 3 },
	{ 10, 2, 6 },
	{ 1, 1, 2 },
	{ 3, 3, 0 },
	{ 8, 0, 4 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 1, 1, 2 },
	{ 9, 1, 5 },
	{ 0, 0, 1 },
	{ 3, 3, 0 },
	{ 8, 0, 4 },
};

ndInt32 ndIsoSurface::ndImplementation::m_faces[][3] =
{
	{ 0, 8, 3 },
	{ 0, 1, 9 },
	{ 1, 8, 3 },
	{ 9, 8, 1 },
	{ 1, 2, 10 },
	{ 0, 8, 3 },
	{ 1, 2, 10 },
	{ 9, 2, 10 },
	{ 0, 2, 9 },
	{ 2, 8, 3 },
	{ 2, 10, 8 },
	{ 10, 9, 8 },
	{ 3, 11, 2 },
	{ 0, 11, 2 },
	{ 8, 11, 0 },
	{ 1, 9, 0 },
	{ 2, 3, 11 },
	{ 1, 11, 2 },
	{ 1, 9, 11 },
	{ 9, 8, 11 },
	{ 3, 10, 1 },
	{ 11, 10, 3 },
	{ 0, 10, 1 },
	{ 0, 8, 10 },
	{ 8, 11, 10 },
	{ 3, 9, 0 },
	{ 3, 11, 9 },
	{ 11, 10, 9 },
	{ 9, 8, 10 },
	{ 10, 8, 11 },
	{ 4, 7, 8 },
	{ 4, 3, 0 },
	{ 7, 3, 4 },
	{ 0, 1, 9 },
	{ 8, 4, 7 },
	{ 4, 1, 9 },
	{ 4, 7, 1 },
	{ 7, 3, 1 },
	{ 1, 2, 10 },
	{ 8, 4, 7 },
	{ 3, 4, 7 },
	{ 3, 0, 4 },
	{ 1, 2, 10 },
	{ 9, 2, 10 },
	{ 9, 0, 2 },
	{ 8, 4, 7 },
	{ 2, 10, 9 },
	{ 2, 9, 7 },
	{ 2, 7, 3 },
	{ 7, 9, 4 },
	{ 8, 4, 7 },
	{ 3, 11, 2 },
	{ 11, 4, 7 },
	{ 11, 2, 4 },
	{ 2, 0, 4 },
	{ 9, 0, 1 },
	{ 8, 4, 7 },
	{ 2, 3, 11 },
	{ 4, 7, 11 },
	{ 9, 4, 11 },
	{ 9, 11, 2 },
	{ 9, 2, 1 },
	{ 3, 10, 1 },
	{ 3, 11, 10 },
	{ 7, 8, 4 },
	{ 1, 11, 10 },
	{ 1, 4, 11 },
	{ 1, 0, 4 },
	{ 7, 11, 4 },
	{ 4, 7, 8 },
	{ 9, 0, 11 },
	{ 9, 11, 10 },
	{ 11, 0, 3 },
	{ 4, 7, 11 },
	{ 4, 11, 9 },
	{ 9, 11, 10 },
	{ 9, 5, 4 },
	{ 9, 5, 4 },
	{ 0, 8, 3 },
	{ 0, 5, 4 },
	{ 1, 5, 0 },
	{ 8, 5, 4 },
	{ 8, 3, 5 },
	{ 3, 1, 5 },
	{ 1, 2, 10 },
	{ 9, 5, 4 },
	{ 3, 0, 8 },
	{ 1, 2, 10 },
	{ 4, 9, 5 },
	{ 5, 2, 10 },
	{ 5, 4, 2 },
	{ 4, 0, 2 },
	{ 2, 10, 5 },
	{ 3, 2, 5 },
	{ 3, 5, 4 },
	{ 3, 4, 8 },
	{ 9, 5, 4 },
	{ 2, 3, 11 },
	{ 0, 11, 2 },
	{ 0, 8, 11 },
	{ 4, 9, 5 },
	{ 0, 5, 4 },
	{ 0, 1, 5 },
	{ 2, 3, 11 },
	{ 2, 1, 5 },
	{ 2, 5, 8 },
	{ 2, 8, 11 },
	{ 4, 8, 5 },
	{ 10, 3, 11 },
	{ 10, 1, 3 },
	{ 9, 5, 4 },
	{ 4, 9, 5 },
	{ 0, 8, 1 },
	{ 8, 10, 1 },
	{ 8, 11, 10 },
	{ 5, 4, 0 },
	{ 5, 0, 11 },
	{ 5, 11, 10 },
	{ 11, 0, 3 },
	{ 5, 4, 8 },
	{ 5, 8, 10 },
	{ 10, 8, 11 },
	{ 9, 7, 8 },
	{ 5, 7, 9 },
	{ 9, 3, 0 },
	{ 9, 5, 3 },
	{ 5, 7, 3 },
	{ 0, 7, 8 },
	{ 0, 1, 7 },
	{ 1, 5, 7 },
	{ 1, 5, 3 },
	{ 3, 5, 7 },
	{ 9, 7, 8 },
	{ 9, 5, 7 },
	{ 10, 1, 2 },
	{ 10, 1, 2 },
	{ 9, 5, 0 },
	{ 5, 3, 0 },
	{ 5, 7, 3 },
	{ 8, 0, 2 },
	{ 8, 2, 5 },
	{ 8, 5, 7 },
	{ 10, 5, 2 },
	{ 2, 10, 5 },
	{ 2, 5, 3 },
	{ 3, 5, 7 },
	{ 7, 9, 5 },
	{ 7, 8, 9 },
	{ 3, 11, 2 },
	{ 9, 5, 7 },
	{ 9, 7, 2 },
	{ 9, 2, 0 },
	{ 2, 7, 11 },
	{ 2, 3, 11 },
	{ 0, 1, 8 },
	{ 1, 7, 8 },
	{ 1, 5, 7 },
	{ 11, 2, 1 },
	{ 11, 1, 7 },
	{ 7, 1, 5 },
	{ 9, 5, 8 },
	{ 8, 5, 7 },
	{ 10, 1, 3 },
	{ 10, 3, 11 },
	{ 5, 7, 0 },
	{ 5, 0, 9 },
	{ 7, 11, 0 },
	{ 1, 0, 10 },
	{ 11, 10, 0 },
	{ 11, 10, 0 },
	{ 11, 0, 3 },
	{ 10, 5, 0 },
	{ 8, 0, 7 },
	{ 5, 7, 0 },
	{ 11, 10, 5 },
	{ 7, 11, 5 },
	{ 10, 6, 5 },
	{ 0, 8, 3 },
	{ 5, 10, 6 },
	{ 9, 0, 1 },
	{ 5, 10, 6 },
	{ 1, 8, 3 },
	{ 1, 9, 8 },
	{ 5, 10, 6 },
	{ 1, 6, 5 },
	{ 2, 6, 1 },
	{ 1, 6, 5 },
	{ 1, 2, 6 },
	{ 3, 0, 8 },
	{ 9, 6, 5 },
	{ 9, 0, 6 },
	{ 0, 2, 6 },
	{ 5, 9, 8 },
	{ 5, 8, 2 },
	{ 5, 2, 6 },
	{ 3, 2, 8 },
	{ 2, 3, 11 },
	{ 10, 6, 5 },
	{ 11, 0, 8 },
	{ 11, 2, 0 },
	{ 10, 6, 5 },
	{ 0, 1, 9 },
	{ 2, 3, 11 },
	{ 5, 10, 6 },
	{ 5, 10, 6 },
	{ 1, 9, 2 },
	{ 9, 11, 2 },
	{ 9, 8, 11 },
	{ 6, 3, 11 },
	{ 6, 5, 3 },
	{ 5, 1, 3 },
	{ 0, 8, 11 },
	{ 0, 11, 5 },
	{ 0, 5, 1 },
	{ 5, 11, 6 },
	{ 3, 11, 6 },
	{ 0, 3, 6 },
	{ 0, 6, 5 },
	{ 0, 5, 9 },
	{ 6, 5, 9 },
	{ 6, 9, 11 },
	{ 11, 9, 8 },
	{ 5, 10, 6 },
	{ 4, 7, 8 },
	{ 4, 3, 0 },
	{ 4, 7, 3 },
	{ 6, 5, 10 },
	{ 1, 9, 0 },
	{ 5, 10, 6 },
	{ 8, 4, 7 },
	{ 10, 6, 5 },
	{ 1, 9, 7 },
	{ 1, 7, 3 },
	{ 7, 9, 4 },
	{ 6, 1, 2 },
	{ 6, 5, 1 },
	{ 4, 7, 8 },
	{ 1, 2, 5 },
	{ 5, 2, 6 },
	{ 3, 0, 4 },
	{ 3, 4, 7 },
	{ 8, 4, 7 },
	{ 9, 0, 5 },
	{ 0, 6, 5 },
	{ 0, 2, 6 },
	{ 7, 3, 9 },
	{ 7, 9, 4 },
	{ 3, 2, 9 },
	{ 5, 9, 6 },
	{ 2, 6, 9 },
	{ 3, 11, 2 },
	{ 7, 8, 4 },
	{ 10, 6, 5 },
	{ 5, 10, 6 },
	{ 4, 7, 2 },
	{ 4, 2, 0 },
	{ 2, 7, 11 },
	{ 0, 1, 9 },
	{ 4, 7, 8 },
	{ 2, 3, 11 },
	{ 5, 10, 6 },
	{ 9, 2, 1 },
	{ 9, 11, 2 },
	{ 9, 4, 11 },
	{ 7, 11, 4 },
	{ 5, 10, 6 },
	{ 8, 4, 7 },
	{ 3, 11, 5 },
	{ 3, 5, 1 },
	{ 5, 11, 6 },
	{ 5, 1, 11 },
	{ 5, 11, 6 },
	{ 1, 0, 11 },
	{ 7, 11, 4 },
	{ 0, 4, 11 },
	{ 0, 5, 9 },
	{ 0, 6, 5 },
	{ 0, 3, 6 },
	{ 11, 6, 3 },
	{ 8, 4, 7 },
	{ 6, 5, 9 },
	{ 6, 9, 11 },
	{ 4, 7, 9 },
	{ 7, 11, 9 },
	{ 10, 4, 9 },
	{ 6, 4, 10 },
	{ 4, 10, 6 },
	{ 4, 9, 10 },
	{ 0, 8, 3 },
	{ 10, 0, 1 },
	{ 10, 6, 0 },
	{ 6, 4, 0 },
	{ 8, 3, 1 },
	{ 8, 1, 6 },
	{ 8, 6, 4 },
	{ 6, 1, 10 },
	{ 1, 4, 9 },
	{ 1, 2, 4 },
	{ 2, 6, 4 },
	{ 3, 0, 8 },
	{ 1, 2, 9 },
	{ 2, 4, 9 },
	{ 2, 6, 4 },
	{ 0, 2, 4 },
	{ 4, 2, 6 },
	{ 8, 3, 2 },
	{ 8, 2, 4 },
	{ 4, 2, 6 },
	{ 10, 4, 9 },
	{ 10, 6, 4 },
	{ 11, 2, 3 },
	{ 0, 8, 2 },
	{ 2, 8, 11 },
	{ 4, 9, 10 },
	{ 4, 10, 6 },
	{ 3, 11, 2 },
	{ 0, 1, 6 },
	{ 0, 6, 4 },
	{ 6, 1, 10 },
	{ 6, 4, 1 },
	{ 6, 1, 10 },
	{ 4, 8, 1 },
	{ 2, 1, 11 },
	{ 8, 11, 1 },
	{ 9, 6, 4 },
	{ 9, 3, 6 },
	{ 9, 1, 3 },
	{ 11, 6, 3 },
	{ 8, 11, 1 },
	{ 8, 1, 0 },
	{ 11, 6, 1 },
	{ 9, 1, 4 },
	{ 6, 4, 1 },
	{ 3, 11, 6 },
	{ 3, 6, 0 },
	{ 0, 6, 4 },
	{ 6, 4, 8 },
	{ 11, 6, 8 },
	{ 7, 10, 6 },
	{ 7, 8, 10 },
	{ 8, 9, 10 },
	{ 0, 7, 3 },
	{ 0, 10, 7 },
	{ 0, 9, 10 },
	{ 6, 7, 10 },
	{ 10, 6, 7 },
	{ 1, 10, 7 },
	{ 1, 7, 8 },
	{ 1, 8, 0 },
	{ 10, 6, 7 },
	{ 10, 7, 1 },
	{ 1, 7, 3 },
	{ 1, 2, 6 },
	{ 1, 6, 8 },
	{ 1, 8, 9 },
	{ 8, 6, 7 },
	{ 2, 6, 9 },
	{ 2, 9, 1 },
	{ 6, 7, 9 },
	{ 0, 9, 3 },
	{ 7, 3, 9 },
	{ 7, 8, 0 },
	{ 7, 0, 6 },
	{ 6, 0, 2 },
	{ 7, 3, 2 },
	{ 6, 7, 2 },
	{ 2, 3, 11 },
	{ 10, 6, 8 },
	{ 10, 8, 9 },
	{ 8, 6, 7 },
	{ 2, 0, 7 },
	{ 2, 7, 11 },
	{ 0, 9, 7 },
	{ 6, 7, 10 },
	{ 9, 10, 7 },
	{ 1, 8, 0 },
	{ 1, 7, 8 },
	{ 1, 10, 7 },
	{ 6, 7, 10 },
	{ 2, 3, 11 },
	{ 11, 2, 1 },
	{ 11, 1, 7 },
	{ 10, 6, 1 },
	{ 6, 7, 1 },
	{ 8, 9, 6 },
	{ 8, 6, 7 },
	{ 9, 1, 6 },
	{ 11, 6, 3 },
	{ 1, 3, 6 },
	{ 0, 9, 1 },
	{ 11, 6, 7 },
	{ 7, 8, 0 },
	{ 7, 0, 6 },
	{ 3, 11, 0 },
	{ 11, 6, 0 },
	{ 7, 11, 6 },
	{ 7, 6, 11 },
	{ 3, 0, 8 },
	{ 11, 7, 6 },
	{ 0, 1, 9 },
	{ 11, 7, 6 },
	{ 8, 1, 9 },
	{ 8, 3, 1 },
	{ 11, 7, 6 },
	{ 10, 1, 2 },
	{ 6, 11, 7 },
	{ 1, 2, 10 },
	{ 3, 0, 8 },
	{ 6, 11, 7 },
	{ 2, 9, 0 },
	{ 2, 10, 9 },
	{ 6, 11, 7 },
	{ 6, 11, 7 },
	{ 2, 10, 3 },
	{ 10, 8, 3 },
	{ 10, 9, 8 },
	{ 7, 2, 3 },
	{ 6, 2, 7 },
	{ 7, 0, 8 },
	{ 7, 6, 0 },
	{ 6, 2, 0 },
	{ 2, 7, 6 },
	{ 2, 3, 7 },
	{ 0, 1, 9 },
	{ 1, 6, 2 },
	{ 1, 8, 6 },
	{ 1, 9, 8 },
	{ 8, 7, 6 },
	{ 10, 7, 6 },
	{ 10, 1, 7 },
	{ 1, 3, 7 },
	{ 10, 7, 6 },
	{ 1, 7, 10 },
	{ 1, 8, 7 },
	{ 1, 0, 8 },
	{ 0, 3, 7 },
	{ 0, 7, 10 },
	{ 0, 10, 9 },
	{ 6, 10, 7 },
	{ 7, 6, 10 },
	{ 7, 10, 8 },
	{ 8, 10, 9 },
	{ 6, 8, 4 },
	{ 11, 8, 6 },
	{ 3, 6, 11 },
	{ 3, 0, 6 },
	{ 0, 4, 6 },
	{ 8, 6, 11 },
	{ 8, 4, 6 },
	{ 9, 0, 1 },
	{ 9, 4, 6 },
	{ 9, 6, 3 },
	{ 9, 3, 1 },
	{ 11, 3, 6 },
	{ 6, 8, 4 },
	{ 6, 11, 8 },
	{ 2, 10, 1 },
	{ 1, 2, 10 },
	{ 3, 0, 11 },
	{ 0, 6, 11 },
	{ 0, 4, 6 },
	{ 4, 11, 8 },
	{ 4, 6, 11 },
	{ 0, 2, 9 },
	{ 2, 10, 9 },
	{ 10, 9, 3 },
	{ 10, 3, 2 },
	{ 9, 4, 3 },
	{ 11, 3, 6 },
	{ 4, 6, 3 },
	{ 8, 2, 3 },
	{ 8, 4, 2 },
	{ 4, 6, 2 },
	{ 0, 4, 2 },
	{ 4, 6, 2 },
	{ 1, 9, 0 },
	{ 2, 3, 4 },
	{ 2, 4, 6 },
	{ 4, 3, 8 },
	{ 1, 9, 4 },
	{ 1, 4, 2 },
	{ 2, 4, 6 },
	{ 8, 1, 3 },
	{ 8, 6, 1 },
	{ 8, 4, 6 },
	{ 6, 10, 1 },
	{ 10, 1, 0 },
	{ 10, 0, 6 },
	{ 6, 0, 4 },
	{ 4, 6, 3 },
	{ 4, 3, 8 },
	{ 6, 10, 3 },
	{ 0, 3, 9 },
	{ 10, 9, 3 },
	{ 10, 9, 4 },
	{ 6, 10, 4 },
	{ 4, 9, 5 },
	{ 7, 6, 11 },
	{ 0, 8, 3 },
	{ 4, 9, 5 },
	{ 11, 7, 6 },
	{ 5, 0, 1 },
	{ 5, 4, 0 },
	{ 7, 6, 11 },
	{ 11, 7, 6 },
	{ 8, 3, 4 },
	{ 3, 5, 4 },
	{ 3, 1, 5 },
	{ 9, 5, 4 },
	{ 10, 1, 2 },
	{ 7, 6, 11 },
	{ 6, 11, 7 },
	{ 1, 2, 10 },
	{ 0, 8, 3 },
	{ 4, 9, 5 },
	{ 7, 6, 11 },
	{ 5, 4, 10 },
	{ 4, 2, 10 },
	{ 4, 0, 2 },
	{ 3, 4, 8 },
	{ 3, 5, 4 },
	{ 3, 2, 5 },
	{ 10, 5, 2 },
	{ 11, 7, 6 },
	{ 7, 2, 3 },
	{ 7, 6, 2 },
	{ 5, 4, 9 },
	{ 9, 5, 4 },
	{ 0, 8, 6 },
	{ 0, 6, 2 },
	{ 6, 8, 7 },
	{ 3, 6, 2 },
	{ 3, 7, 6 },
	{ 1, 5, 0 },
	{ 5, 4, 0 },
	{ 6, 2, 8 },
	{ 6, 8, 7 },
	{ 2, 1, 8 },
	{ 4, 8, 5 },
	{ 1, 5, 8 },
	{ 9, 5, 4 },
	{ 10, 1, 6 },
	{ 1, 7, 6 },
	{ 1, 3, 7 },
	{ 1, 6, 10 },
	{ 1, 7, 6 },
	{ 1, 0, 7 },
	{ 8, 7, 0 },
	{ 9, 5, 4 },
	{ 4, 0, 10 },
	{ 4, 10, 5 },
	{ 0, 3, 10 },
	{ 6, 10, 7 },
	{ 3, 7, 10 },
	{ 7, 6, 10 },
	{ 7, 10, 8 },
	{ 5, 4, 10 },
	{ 4, 8, 10 },
	{ 6, 9, 5 },
	{ 6, 11, 9 },
	{ 11, 8, 9 },
	{ 3, 6, 11 },
	{ 0, 6, 3 },
	{ 0, 5, 6 },
	{ 0, 9, 5 },
	{ 0, 11, 8 },
	{ 0, 5, 11 },
	{ 0, 1, 5 },
	{ 5, 6, 11 },
	{ 6, 11, 3 },
	{ 6, 3, 5 },
	{ 5, 3, 1 },
	{ 1, 2, 10 },
	{ 9, 5, 11 },
	{ 9, 11, 8 },
	{ 11, 5, 6 },
	{ 0, 11, 3 },
	{ 0, 6, 11 },
	{ 0, 9, 6 },
	{ 5, 6, 9 },
	{ 1, 2, 10 },
	{ 11, 8, 5 },
	{ 11, 5, 6 },
	{ 8, 0, 5 },
	{ 10, 5, 2 },
	{ 0, 2, 5 },
	{ 6, 11, 3 },
	{ 6, 3, 5 },
	{ 2, 10, 3 },
	{ 10, 5, 3 },
	{ 5, 8, 9 },
	{ 5, 2, 8 },
	{ 5, 6, 2 },
	{ 3, 8, 2 },
	{ 9, 5, 6 },
	{ 9, 6, 0 },
	{ 0, 6, 2 },
	{ 1, 5, 8 },
	{ 1, 8, 0 },
	{ 5, 6, 8 },
	{ 3, 8, 2 },
	{ 6, 2, 8 },
	{ 1, 5, 6 },
	{ 2, 1, 6 },
	{ 1, 3, 6 },
	{ 1, 6, 10 },
	{ 3, 8, 6 },
	{ 5, 6, 9 },
	{ 8, 9, 6 },
	{ 10, 1, 0 },
	{ 10, 0, 6 },
	{ 9, 5, 0 },
	{ 5, 6, 0 },
	{ 0, 3, 8 },
	{ 5, 6, 10 },
	{ 10, 5, 6 },
	{ 11, 5, 10 },
	{ 7, 5, 11 },
	{ 11, 5, 10 },
	{ 11, 7, 5 },
	{ 8, 3, 0 },
	{ 5, 11, 7 },
	{ 5, 10, 11 },
	{ 1, 9, 0 },
	{ 10, 7, 5 },
	{ 10, 11, 7 },
	{ 9, 8, 1 },
	{ 8, 3, 1 },
	{ 11, 1, 2 },
	{ 11, 7, 1 },
	{ 7, 5, 1 },
	{ 0, 8, 3 },
	{ 1, 2, 7 },
	{ 1, 7, 5 },
	{ 7, 2, 11 },
	{ 9, 7, 5 },
	{ 9, 2, 7 },
	{ 9, 0, 2 },
	{ 2, 11, 7 },
	{ 7, 5, 2 },
	{ 7, 2, 11 },
	{ 5, 9, 2 },
	{ 3, 2, 8 },
	{ 9, 8, 2 },
	{ 2, 5, 10 },
	{ 2, 3, 5 },
	{ 3, 7, 5 },
	{ 8, 2, 0 },
	{ 8, 5, 2 },
	{ 8, 7, 5 },
	{ 10, 2, 5 },
	{ 9, 0, 1 },
	{ 5, 10, 3 },
	{ 5, 3, 7 },
	{ 3, 10, 2 },
	{ 9, 8, 2 },
	{ 9, 2, 1 },
	{ 8, 7, 2 },
	{ 10, 2, 5 },
	{ 7, 5, 2 },
	{ 1, 3, 5 },
	{ 3, 7, 5 },
	{ 0, 8, 7 },
	{ 0, 7, 1 },
	{ 1, 7, 5 },
	{ 9, 0, 3 },
	{ 9, 3, 5 },
	{ 5, 3, 7 },
	{ 9, 8, 7 },
	{ 5, 9, 7 },
	{ 5, 8, 4 },
	{ 5, 10, 8 },
	{ 10, 11, 8 },
	{ 5, 0, 4 },
	{ 5, 11, 0 },
	{ 5, 10, 11 },
	{ 11, 3, 0 },
	{ 0, 1, 9 },
	{ 8, 4, 10 },
	{ 8, 10, 11 },
	{ 10, 4, 5 },
	{ 10, 11, 4 },
	{ 10, 4, 5 },
	{ 11, 3, 4 },
	{ 9, 4, 1 },
	{ 3, 1, 4 },
	{ 2, 5, 1 },
	{ 2, 8, 5 },
	{ 2, 11, 8 },
	{ 4, 5, 8 },
	{ 0, 4, 11 },
	{ 0, 11, 3 },
	{ 4, 5, 11 },
	{ 2, 11, 1 },
	{ 5, 1, 11 },
	{ 0, 2, 5 },
	{ 0, 5, 9 },
	{ 2, 11, 5 },
	{ 4, 5, 8 },
	{ 11, 8, 5 },
	{ 9, 4, 5 },
	{ 2, 11, 3 },
	{ 2, 5, 10 },
	{ 3, 5, 2 },
	{ 3, 4, 5 },
	{ 3, 8, 4 },
	{ 5, 10, 2 },
	{ 5, 2, 4 },
	{ 4, 2, 0 },
	{ 3, 10, 2 },
	{ 3, 5, 10 },
	{ 3, 8, 5 },
	{ 4, 5, 8 },
	{ 0, 1, 9 },
	{ 5, 10, 2 },
	{ 5, 2, 4 },
	{ 1, 9, 2 },
	{ 9, 4, 2 },
	{ 8, 4, 5 },
	{ 8, 5, 3 },
	{ 3, 5, 1 },
	{ 0, 4, 5 },
	{ 1, 0, 5 },
	{ 8, 4, 5 },
	{ 8, 5, 3 },
	{ 9, 0, 5 },
	{ 0, 3, 5 },
	{ 9, 4, 5 },
	{ 4, 11, 7 },
	{ 4, 9, 11 },
	{ 9, 10, 11 },
	{ 0, 8, 3 },
	{ 4, 9, 7 },
	{ 9, 11, 7 },
	{ 9, 10, 11 },
	{ 1, 10, 11 },
	{ 1, 11, 4 },
	{ 1, 4, 0 },
	{ 7, 4, 11 },
	{ 3, 1, 4 },
	{ 3, 4, 8 },
	{ 1, 10, 4 },
	{ 7, 4, 11 },
	{ 10, 11, 4 },
	{ 4, 11, 7 },
	{ 9, 11, 4 },
	{ 9, 2, 11 },
	{ 9, 1, 2 },
	{ 9, 7, 4 },
	{ 9, 11, 7 },
	{ 9, 1, 11 },
	{ 2, 11, 1 },
	{ 0, 8, 3 },
	{ 11, 7, 4 },
	{ 11, 4, 2 },
	{ 2, 4, 0 },
	{ 11, 7, 4 },
	{ 11, 4, 2 },
	{ 8, 3, 4 },
	{ 3, 2, 4 },
	{ 2, 9, 10 },
	{ 2, 7, 9 },
	{ 2, 3, 7 },
	{ 7, 4, 9 },
	{ 9, 10, 7 },
	{ 9, 7, 4 },
	{ 10, 2, 7 },
	{ 8, 7, 0 },
	{ 2, 0, 7 },
	{ 3, 7, 10 },
	{ 3, 10, 2 },
	{ 7, 4, 10 },
	{ 1, 10, 0 },
	{ 4, 0, 10 },
	{ 1, 10, 2 },
	{ 8, 7, 4 },
	{ 4, 9, 1 },
	{ 4, 1, 7 },
	{ 7, 1, 3 },
	{ 4, 9, 1 },
	{ 4, 1, 7 },
	{ 0, 8, 1 },
	{ 8, 7, 1 },
	{ 4, 0, 3 },
	{ 7, 4, 3 },
	{ 4, 8, 7 },
	{ 9, 10, 8 },
	{ 10, 11, 8 },
	{ 3, 0, 9 },
	{ 3, 9, 11 },
	{ 11, 9, 10 },
	{ 0, 1, 10 },
	{ 0, 10, 8 },
	{ 8, 10, 11 },
	{ 3, 1, 10 },
	{ 11, 3, 10 },
	{ 1, 2, 11 },
	{ 1, 11, 9 },
	{ 9, 11, 8 },
	{ 3, 0, 9 },
	{ 3, 9, 11 },
	{ 1, 2, 9 },
	{ 2, 11, 9 },
	{ 0, 2, 11 },
	{ 8, 0, 11 },
	{ 3, 2, 11 },
	{ 2, 3, 8 },
	{ 2, 8, 10 },
	{ 10, 8, 9 },
	{ 9, 10, 2 },
	{ 0, 9, 2 },
	{ 2, 3, 8 },
	{ 2, 8, 10 },
	{ 0, 1, 8 },
	{ 1, 10, 8 },
	{ 1, 10, 2 },
	{ 1, 3, 8 },
	{ 9, 1, 8 },
	{ 0, 9, 1 },
	{ 0, 3, 8 },
};

ndVector ndIsoSurface::ndImplementation::m_gridCorners[] =
{
	ndVector(ndFloat32(0.0f), ndFloat32(-1.0f), ndFloat32(-1.0f), ndFloat32(0.0f)),
	ndVector(ndFloat32(0.0f), ndFloat32(-1.0f), ndFloat32(0.0f), ndFloat32(0.0f)),
	ndVector(ndFloat32(-1.0f), ndFloat32(-1.0f), ndFloat32(0.0f), ndFloat32(0.0f)),
	ndVector(ndFloat32(-1.0f), ndFloat32(-1.0f), ndFloat32(-1.0f), ndFloat32(0.0f)),
	ndVector(ndFloat32(0.0f), ndFloat32(0.0f), ndFloat32(-1.0f), ndFloat32(0.0f)),
	ndVector(ndFloat32(0.0f), ndFloat32(0.0f), ndFloat32(0.0f), ndFloat32(0.0f)),
	ndVector(ndFloat32(-1.0f), ndFloat32(0.0f), ndFloat32(0.0f), ndFloat32(0.0f)),
	ndVector(ndFloat32(-1.0f), ndFloat32(0.0f), ndFloat32(-1.0f), ndFloat32(0.0f))
};

inline ndIsoSurface::ndImplementation::ndImplementation()
	:ndClassAlloc()
	,m_boxP0(ndVector::m_zero)
	,m_boxP1(ndVector::m_zero)
	,m_gridSize(ndVector::m_zero)
	,m_invGridSize(ndVector::m_zero)
	,m_hashGridMap(256)
	,m_hashGridMapScratchBuffer(256)
	,m_triangles(256)
	,m_trianglesScratchBuffer(256)
	,m_isoValue(ndFloat32 (0.5f))
	//,m_worlToGridOrigin(ndFloat32(1.0f))
	//,m_worlToGridScale(ndFloat32(1.0f))
	,m_volumeSizeX(1)
	,m_volumeSizeY(1)
	,m_volumeSizeZ(1)
	,m_upperDigitsIsValid()
{
}

ndIsoSurface::ndImplementation::~ndImplementation()
{
}

ndVector ndIsoSurface::ndImplementation::GetOrigin() const
{
	return m_boxP0;
}

void ndIsoSurface::ndImplementation::Clear()
{
	m_triangles.Resize(256);
	m_hashGridMap.Resize(256);
	m_trianglesScratchBuffer.Resize(256);
	m_hashGridMapScratchBuffer.Resize(256);
}

void ndIsoSurface::ndImplementation::CalculateAabb(const ndArray<ndVector>& points, ndFloat32 gridSize)
{
	D_TRACKTIME();

	m_isoValue = ndFloat32(0.5f);
	m_gridSize = ndVector::m_triplexMask & ndVector(gridSize);
	m_invGridSize = ndVector::m_triplexMask & ndVector(ndFloat32(1.0f) / gridSize);

	ndVector boxP0(ndFloat32(1.0e10f));
	ndVector boxP1(ndFloat32(-1.0e10f));
	for (ndInt32 i = 0; i < points.GetCount(); ++i)
	{
		boxP0 = boxP0.GetMin(points[i]);
		boxP1 = boxP1.GetMax(points[i]);
	}
	boxP0 -= m_gridSize;
	boxP1 += (m_gridSize + m_gridSize);

	// quantize the aabb to integers of the gird size
	boxP0 = m_gridSize * (boxP0 * m_invGridSize).Floor();
	boxP1 = m_gridSize * (boxP1 * m_invGridSize).Floor();

	// make sure the w component is zero.
	m_boxP0 = boxP0 & ndVector::m_triplexMask;
	m_boxP1 = boxP1 & ndVector::m_triplexMask;

	const ndVector sizeInGrids(((boxP1 - boxP0) * m_invGridSize + ndVector::m_one).Floor().GetInt());
	m_volumeSizeX = ndInt32(sizeInGrids.m_ix);
	m_volumeSizeY = ndInt32(sizeInGrids.m_iy);
	m_volumeSizeZ = ndInt32(sizeInGrids.m_iz);

	//m_worlToGridOrigin = m_boxP0.m_x;
	//m_worlToGridScale = ndFloat32(1 << D_GRID_X_RESOLUTION) * m_volumeSizeX / (m_boxP1.m_x - m_boxP0.m_x);
}

ndVector ndIsoSurface::ndImplementation::InterpolateLowResVertex(const ndVector& p0, const ndVector& p1) const
{
	ndAssert(ndAbs(p1.m_w - p0.m_w) == ndFloat32(1.0f));
	const ndVector p1p0(p1 - p0);
	return ndVector(p0 + p1p0 * ndVector::m_half);
}

ndVector ndIsoSurface::ndImplementation::InterpolateHighResVertex(ndFloat32, const ndVector& p0, const ndVector& p1) const
{
	//ndVector p;
	//ndFloat32 mu = (isolevel - p0.m_w) / (p1.m_w - p0.m_w);
	//p.m_x = p0.m_x + mu * (p1.m_x - p0.m_x);
	//p.m_y = p0.m_y + mu * (p1.m_y - p0.m_y);
	//p.m_z = p0.m_z + mu * (p1.m_z - p0.m_z);
	//p.m_w = ndFloat32(0.0f);
	//return p;

	//ndAssert(isolevel == ndFloat32(0.5f));
	ndAssert(ndAbs(p1.m_w - p0.m_w) == ndFloat32(1.0f));
	const ndVector p1p0(p1 - p0);
	return ndVector(p0 + p1p0 * ndVector::m_half);
}

void ndIsoSurface::ndImplementation::ProcessLowResCell(ndIsoCell& cell)
{
	ndInt32 tableIndex = 0;
	for (ndInt32 i = 0; i < 8; ++i)
	{
		tableIndex |= (cell.m_isoValues[i].m_w > m_isoValue) << i;
	}

	ndVector vertlist[12];
	const ndInt32 start = m_edgeScan[tableIndex];
	const ndInt32 edgeCount = m_edgeScan[tableIndex + 1] - start;
	for (ndInt32 i = 0; i < edgeCount; ++i)
	{
		const ndEdge& edge = m_edges[start + i];
		const ndInt32 midPoint = edge.m_midPoint;
		const ndInt32 p0 = edge.m_p0;
		const ndInt32 p1 = edge.m_p1;
		vertlist[midPoint] = InterpolateLowResVertex(cell.m_isoValues[p0], cell.m_isoValues[p1]);
	}
	
	const ndInt32 index = ndInt32 (m_triangles.GetCount());
	const ndInt32 faceStart = m_facesScan[tableIndex];
	const ndInt32 faceVertexCount = m_facesScan[tableIndex + 1] - faceStart;
	
	m_triangles.SetCount(index + faceVertexCount * 3);
	ndVector* const triangle = &m_triangles[index];
	for (ndInt32 i = 0; i < faceVertexCount; ++i)
	{
		const ndInt32 j = i * 3;
		const ndInt32 j0 = m_faces[faceStart + i][0];
		const ndInt32 j1 = m_faces[faceStart + i][1];
		const ndInt32 j2 = m_faces[faceStart + i][2];
		
		triangle[j + 0] = vertlist[j0];
		triangle[j + 1] = vertlist[j1];
		triangle[j + 2] = vertlist[j2];
		triangle[j + 0].m_w = ndFloat32(index + j + 0);
		triangle[j + 1].m_w = ndFloat32(index + j + 1);
		triangle[j + 2].m_w = ndFloat32(index + j + 2);
	}
}

void ndIsoSurface::ndImplementation::ProcessHighResCell(ndIsoCell& cell, ndCalculateIsoValue* const computeIsoValue)
{
	ndInt32 tableIndex = 0;
	for (ndInt32 i = 0; i < 8; ++i)
	{
		const ndVector point(cell.m_isoValues[i] * m_gridSize);
		cell.m_isoValues[i].m_w = computeIsoValue->CalculateIsoValue(point);
		tableIndex |= (cell.m_isoValues[i].m_w > m_isoValue) << i;
	}

	ndVector vertlist[12];
	const ndInt32 start = m_edgeScan[tableIndex];
	const ndInt32 edgeCount = m_edgeScan[tableIndex + 1] - start;
	for (ndInt32 i = 0; i < edgeCount; ++i)
	{
		const ndEdge& edge = m_edges[start + i];
		const ndInt32 midPoint = edge.m_midPoint;
		const ndInt32 p0 = edge.m_p0;
		const ndInt32 p1 = edge.m_p1;
		vertlist[midPoint] = InterpolateHighResVertex(m_isoValue, cell.m_isoValues[p0], cell.m_isoValues[p1]);
	}

	const ndInt32 index = ndInt32 (m_triangles.GetCount());
	const ndInt32 faceStart = m_facesScan[tableIndex];
	const ndInt32 faceVertexCount = m_facesScan[tableIndex + 1] - faceStart;

	m_triangles.SetCount(index + faceVertexCount * 3);
	ndVector* const triangle = &m_triangles[index];
	for (ndInt32 i = 0; i < faceVertexCount; ++i)
	{
		const ndInt32 j = i * 3;
		const ndInt32 j0 = m_faces[faceStart + i][0];
		const ndInt32 j1 = m_faces[faceStart + i][1];
		const ndInt32 j2 = m_faces[faceStart + i][2];

		triangle[j + 0] = vertlist[j0];
		triangle[j + 1] = vertlist[j1];
		triangle[j + 2] = vertlist[j2];
		triangle[j + 0].m_w = ndFloat32(index + j + 0);
		triangle[j + 1].m_w = ndFloat32(index + j + 1);
		triangle[j + 2].m_w = ndFloat32(index + j + 2);
	}
}

//void ndIsoSurface::ndImplementation::CalculateNormals(ndIsoSurface* const me)
void ndIsoSurface::ndImplementation::CalculateNormals(ndIsoSurface* const)
{
	D_TRACKTIME();
	ndAssert(0);
	//ndArray<ndVector>& normals = me->m_normals;
	//const ndArray<ndVector>& points = me->m_points;
	//const ndArray<ndInt32>& triangles = me->m_triangles;
	//normals.SetCount(points.GetCount());
	//
	//// Set all normals to 0.
	//if (normals.GetCount())
	//{
	//	memset(&normals[0], 0, normals.GetCount() * sizeof(ndVector));
	//
	//	for (ndInt32 i = 0; i < triangles.GetCount(); i += 3)
	//	{
	//		ndInt32 id0 = triangles[i + 0];
	//		ndInt32 id1 = triangles[i + 1];
	//		ndInt32 id2 = triangles[i + 2];
	//		ndVector vec1(points[id1] - points[id0]);
	//		ndVector vec2(points[id2] - points[id0]);
	//		ndVector normal = vec1.CrossProduct(vec2);
	//		normals[id0] += normal;
	//		normals[id1] += normal;
	//		normals[id2] += normal;
	//	}
	//
	//	// Normalize normals.
	//	for (ndInt32 i = 0; i < normals.GetCount(); ++i)
	//	{
	//		normals[i] = normals[i] * normals[i].InvMagSqrt();
	//	}
	//}
}

void ndIsoSurface::ndImplementation::SortCellBuckects()
{
	D_TRACKTIME();
	class ndKey_xlow
	{
		public:
		ndKey_xlow(void* const){}
		ndInt32 GetKey(const ndGridHash& cell) const
		{
			return cell.m_xLow;
		}
	};

	class ndKey_ylow
	{
		public:
		ndKey_ylow(void* const) {}
		ndInt32 GetKey(const ndGridHash& cell) const
		{
			return cell.m_yLow;
		}
	};

	class ndKey_zlow
	{
		public:
		ndKey_zlow(void* const) {}
		ndInt32 GetKey(const ndGridHash& cell) const
		{
			return cell.m_zLow;
		}
	};

	class ndKey_xhigh
	{
		public:
		ndKey_xhigh(void* const) {}
		ndInt32 GetKey(const ndGridHash& cell) const
		{
			return cell.m_xHigh;
		}
	};

	class ndKey_yhigh
	{
		public:
		ndKey_yhigh(void* const) {}
		ndInt32 GetKey(const ndGridHash& cell) const
		{
			return cell.m_yHigh;
		}
	};

	class ndKey_zhigh
	{
		public:
		ndKey_zhigh(void* const) {}
		ndInt32 GetKey(const ndGridHash& cell) const
		{
			return cell.m_zHigh;
		}
	};

	ndCountingSort<ndGridHash, ndKey_xlow, 8>(m_hashGridMap, m_hashGridMapScratchBuffer, nullptr, nullptr);
	if (m_upperDigitsIsValid.m_x)
	{
		ndCountingSort<ndGridHash, ndKey_xhigh, 8>(m_hashGridMap, m_hashGridMapScratchBuffer, nullptr, nullptr);
	}

	ndCountingSort<ndGridHash, ndKey_ylow, 8>(m_hashGridMap, m_hashGridMapScratchBuffer, nullptr, nullptr);
	if (m_upperDigitsIsValid.m_y)
	{
		ndCountingSort<ndGridHash, ndKey_yhigh, 8>(m_hashGridMap, m_hashGridMapScratchBuffer, nullptr, nullptr);
	}

	ndCountingSort<ndGridHash, ndKey_zlow, 8>(m_hashGridMap, m_hashGridMapScratchBuffer, nullptr, nullptr);
	if (m_upperDigitsIsValid.m_z)
	{
		ndCountingSort<ndGridHash, ndKey_zhigh, 8>(m_hashGridMap, m_hashGridMapScratchBuffer, nullptr, nullptr);
	}
}

void ndIsoSurface::ndImplementation::RemoveDuplicates(const ndArray<ndVector>& points)
{
	D_TRACKTIME();
	class ndKey_xlow
	{
		public:
		ndKey_xlow(void* const) {}
		ndInt32 GetKey(const ndGridHash& cell) const
		{
			return cell.m_xLow;
		}
	};

	class ndKey_ylow
	{
		public:
		ndKey_ylow(void* const) {}
		ndInt32 GetKey(const ndGridHash& cell) const
		{
			return cell.m_yLow;
		}
	};

	class ndKey_zlow
	{
		public:
		ndKey_zlow(void* const) {}
		ndInt32 GetKey(const ndGridHash& cell) const
		{
			return cell.m_zLow;
		}
	};

	class ndKey_xhigh
	{
		public:
		ndKey_xhigh(void* const) {}
		ndInt32 GetKey(const ndGridHash& cell) const
		{
			return cell.m_xHigh;
		}
	};

	class ndKey_yhigh
	{
		public:
		ndKey_yhigh(void* const) {}
		ndInt32 GetKey(const ndGridHash& cell) const
		{
			return cell.m_yHigh;
		}
	};

	class ndKey_zhigh
	{
		public:
		ndKey_zhigh(void* const) {}
		ndInt32 GetKey(const ndGridHash& cell) const
		{
			return cell.m_zHigh;
		}
	};

	const ndVector origin(m_boxP0);
	const ndVector invGridSize(m_invGridSize);

	const ndVector rounding(ndVector::m_zero);
	ndUpperDigit upperDigits;
	const ndGridHashSteps steps;
	m_hashGridMapScratchBuffer.SetCount(points.GetCount());
	for (ndInt32 i = 0; i < points.GetCount(); ++i)
	{
		const ndVector r(points[i] - origin);
		const ndVector p(r * invGridSize + rounding);
		const ndGridHash hashKey(p);
		m_hashGridMapScratchBuffer[i] = hashKey;

		upperDigits.m_x = ndMax(upperDigits.m_x, ndInt32(hashKey.m_xHigh));
		upperDigits.m_y = ndMax(upperDigits.m_y, ndInt32(hashKey.m_yHigh));
		upperDigits.m_z = ndMax(upperDigits.m_z, ndInt32(hashKey.m_zHigh));
	}
	m_upperDigitsIsValid = upperDigits;

	ndCountingSort<ndGridHash, ndKey_xlow, 8>(m_hashGridMapScratchBuffer, m_hashGridMap, nullptr, nullptr);
	if (m_upperDigitsIsValid.m_x)
	{
		ndCountingSort<ndGridHash, ndKey_xhigh, 8>(m_hashGridMapScratchBuffer, m_hashGridMap, nullptr, nullptr);
	}

	ndCountingSort<ndGridHash, ndKey_ylow, 8>(m_hashGridMapScratchBuffer, m_hashGridMap, nullptr, nullptr);
	if (m_upperDigitsIsValid.m_y)
	{
		ndCountingSort<ndGridHash, ndKey_yhigh, 8>(m_hashGridMapScratchBuffer, m_hashGridMap, nullptr, nullptr);
	}

	ndCountingSort<ndGridHash, ndKey_zlow, 8>(m_hashGridMapScratchBuffer, m_hashGridMap, nullptr, nullptr);
	if (m_upperDigitsIsValid.m_z)
	{
		ndCountingSort<ndGridHash, ndKey_zhigh, 8>(m_hashGridMapScratchBuffer, m_hashGridMap, nullptr, nullptr);
	}

	ndInt32 gridCount = 0;
	for (ndInt32 i = 1; i < m_hashGridMapScratchBuffer.GetCount(); ++i)
	{
		const ndGridHash cell(m_hashGridMapScratchBuffer[i]);
		gridCount += (cell.m_gridFullHash != m_hashGridMapScratchBuffer[i - 1].m_gridFullHash);
		m_hashGridMapScratchBuffer[gridCount] = cell;
	}
	gridCount++;
	m_hashGridMapScratchBuffer.SetCount(gridCount);
}
	
void ndIsoSurface::ndImplementation::GenerateLowResIsoSurface()
{
	D_TRACKTIME();
	ndInt32 end = 0;
	const ndInt32 gridCount = ndInt32(m_hashGridMap.GetCount());
	m_hashGridMap.PushBack(ndGridHash(0xffff, 0xffff, 0xffff));

	m_triangles.SetCount(0);
	for (ndInt32 i = 0; i < gridCount; i = end)
	{
		end = i + 1;
		ndInt32 start = i;
		const ndGridHash startGrid(m_hashGridMap[start], 0);
		while (startGrid.m_gridCellHash == ndGridHash(m_hashGridMap[end], 0).m_gridCellHash)
		{
			end++;
		}
		ndInt32 count = end - start;
		if (count < 8)
		{
			ndIsoCell cell;
			ndVector* const isoValue = &cell.m_isoValues[0];
			ndVector origin(ndFloat32(startGrid.m_x + 1), ndFloat32(startGrid.m_y + 1), ndFloat32(startGrid.m_z + 1), ndFloat32(0.0f));
			for (ndInt32 j = 0; j < 8; ++j)
			{
				isoValue[j] = origin + m_gridCorners[j];
			}
			for (ndInt32 j = 0; j < count; ++j)
			{
				ndInt32 index = m_hashGridMap[start + j].m_cellType;
				isoValue[index].m_w = ndFloat32(1.0f);
			}
			ProcessLowResCell(cell);
		}
	}
}

void ndIsoSurface::ndImplementation::GenerateHighResIsoSurface(ndCalculateIsoValue* const computeIsoValue)
{
	D_TRACKTIME();
	ndInt32 end = 0;
	const ndInt32 gridCount = ndInt32(m_hashGridMap.GetCount());
	m_hashGridMap.PushBack(ndGridHash(0xffff, 0xffff, 0xffff));

	m_triangles.SetCount(0);
	for (ndInt32 i = 0; i < gridCount; i = end)
	{
		end = i + 1;
		ndInt32 start = i;
		const ndGridHash startGrid(m_hashGridMap[start], 0);
		while (startGrid.m_gridCellHash == ndGridHash(m_hashGridMap[end], 0).m_gridCellHash)
		{
			end++;
		}
		ndInt32 count = end - start;
		if (count < 8)
		{
			ndIsoCell cell;
			ndVector* const isoValue = &cell.m_isoValues[0];
			ndVector origin(ndFloat32(startGrid.m_x + 1), ndFloat32(startGrid.m_y + 1), ndFloat32(startGrid.m_z + 1), ndFloat32(0.0f));
			for (ndInt32 j = 0; j < 8; ++j)
			{
				isoValue[j] = origin + m_gridCorners[j];
			}
			for (ndInt32 j = 0; j < count; ++j)
			{
				ndInt32 index = m_hashGridMap[start + j].m_cellType;
				isoValue[index].m_w = ndFloat32(1.0f);
			}
			ProcessHighResCell(cell, computeIsoValue);
		}
	}
}

ndInt32 ndIsoSurface::ndImplementation::GenerateLowResIndexList(
	const ndIsoSurface* const me, 
	ndInt32* const indexList, ndInt32 strideInFloats, 
	ndReal* const posit, ndReal* const normals)
{
	D_TRACKTIME();
	#define D_LOW_RES_BITS	   1
	#define D_LOW_RES_FRACTION (1 << D_LOW_RES_BITS)

	class ndKey_lowX
	{
		public:
		ndKey_lowX(void* const) {}
		ndInt32 GetKey(const ndVector& point) const
		{
			ndFloat32 val = (point.m_x * D_LOW_RES_FRACTION);
			ndInt32 key = ndInt32(val);
			return key & 0xff;
		}
	};

	class ndKey_midleX
	{
		public:
		ndKey_midleX(void* const) {}
		ndInt32 GetKey(const ndVector& point) const
		{
			ndFloat32 val = point.m_x * ndFloat32(D_LOW_RES_FRACTION);
			ndInt32 key = ndInt32(val) >> 8;
			return key & 0xff;
		}
	};

	class ndKey_highX
	{
		public:
		ndKey_highX(void* const) {}
		ndInt32 GetKey(const ndVector& point) const
		{
			ndFloat32 val = point.m_x * ndFloat32(D_LOW_RES_FRACTION);
			ndInt32 key = ndInt32(val) >> 16;
			return key & 0xff;
		}
	};

	class ndKey_lowY
	{
		public:
		ndKey_lowY(void* const) {}
		ndInt32 GetKey(const ndVector& point) const
		{
			ndFloat32 val = (point.m_y * D_LOW_RES_FRACTION);
			ndInt32 key = ndInt32(val);
			return key & 0xff;
		}
	};

	class ndKey_midleY
	{
		public:
		ndKey_midleY(void* const) {}
		ndInt32 GetKey(const ndVector& point) const
		{
			ndFloat32 val = point.m_y * ndFloat32(D_LOW_RES_FRACTION);
			ndInt32 key = ndInt32(val) >> 8;
			return key & 0xff;
		}
	};

	class ndKey_highY
	{
		public:
		ndKey_highY(void* const) {}
		ndInt32 GetKey(const ndVector& point) const
		{
			ndFloat32 val = point.m_y * ndFloat32(D_LOW_RES_FRACTION);
			ndInt32 key = ndInt32(val) >> 16;
			return key & 0xff;
		}
	};

	class ndKey_lowZ
	{
		public:
		ndKey_lowZ(void* const) {}
		ndInt32 GetKey(const ndVector& point) const
		{
			ndFloat32 val = (point.m_z * D_LOW_RES_FRACTION);
			ndInt32 key = ndInt32(val);
			return key & 0xff;
		}
	};

	class ndKey_midleZ
	{
		public:
		ndKey_midleZ(void* const) {}
		ndInt32 GetKey(const ndVector& point) const
		{
			ndFloat32 val = point.m_z * ndFloat32(D_LOW_RES_FRACTION);
			ndInt32 key = ndInt32(val) >> 8;
			return key & 0xff;
		}
	};

	class ndKey_highZ
	{
		public:
		ndKey_highZ(void* const) {}
		ndInt32 GetKey(const ndVector& point) const
		{
			ndFloat32 val = point.m_z * ndFloat32(D_LOW_RES_FRACTION);
			ndInt32 key = ndInt32(val) >> 16;
			return key & 0xff;
		}
	};

	class ndCompareKey
	{
		public:
		ndCompareKey(const ndVector& base)
			:m_base(base)
		{
		}

		ndInt32 Test(const ndVector& point) const
		{
			const ndVector test(point == m_base);
			return ndInt32 (test.m_ix & test.m_iy & test.m_iz);
		}

		ndVector m_base;
	};

	const ndVector invGrid(ndFloat32(1.0f) / me->m_gridSize);
	const ndArray<ndVector>& points = me->m_points;
	m_triangles.SetCount(points.GetCount());
	for (ndInt32 i = 0; i < points.GetCount(); ++i)
	{
		m_triangles[i] = points[i] * invGrid;
		m_triangles[i].m_w = ndFloat32(i);
	}

	const ndInt32 xDimSize = me->m_volumeSizeX * D_LOW_RES_FRACTION;
	ndCountingSort<ndVector, ndKey_lowX, 8>(m_triangles, m_trianglesScratchBuffer, nullptr, nullptr);
	if (xDimSize >= 256)
	{
		ndCountingSort<ndVector, ndKey_midleX, 8>(m_triangles, m_trianglesScratchBuffer, nullptr, nullptr);
	}
	if (xDimSize >= 256 * 256)
	{
		ndCountingSort<ndVector, ndKey_highX, 8>(m_triangles, m_trianglesScratchBuffer, nullptr, nullptr);
	} 
	
	const ndInt32 yDimSize = me->m_volumeSizeY * D_LOW_RES_FRACTION;
	ndCountingSort<ndVector, ndKey_lowY, 8>(m_triangles, m_trianglesScratchBuffer, nullptr, nullptr);
	if (yDimSize >= 256)
	{
		ndCountingSort<ndVector, ndKey_midleY, 8>(m_triangles, m_trianglesScratchBuffer, nullptr, nullptr);
	}
	if (yDimSize >= 256 * 256)
	{
		ndCountingSort<ndVector, ndKey_highY, 8>(m_triangles, m_trianglesScratchBuffer, nullptr, nullptr);
	}
	
	const ndInt32 zDimSize = me->m_volumeSizeZ * D_LOW_RES_FRACTION;
	ndCountingSort<ndVector, ndKey_lowZ, 8>(m_triangles, m_trianglesScratchBuffer, nullptr, nullptr);
	if (zDimSize >= 256)
	{
		ndCountingSort<ndVector, ndKey_midleZ, 8>(m_triangles, m_trianglesScratchBuffer, nullptr, nullptr);
	}
	if (zDimSize >= 256 * 256)
	{
		ndCountingSort<ndVector, ndKey_highZ, 8>(m_triangles, m_trianglesScratchBuffer, nullptr, nullptr);
	}
	
	const ndInt32 count = ndInt32 (m_triangles.GetCount());
	const ndArray<ndVector>& triangleList = m_triangles;
	
	ndInt32 vertexCount = 0;
	m_triangles.PushBack(ndVector::m_one + (m_triangles[count - 1]));
	for (ndInt32 i = 0; i < count; ++i)
	{
		m_trianglesScratchBuffer[vertexCount] = triangleList[i] * m_gridSize;
		
		const ndCompareKey comparator(m_triangles[i]);
		const ndInt32 index = ndInt32(m_triangles[i].m_w);
		indexList[index] = vertexCount;
		for (i = i + 1; comparator.Test(m_triangles[i]); ++i)
		{
			const ndInt32 duplicateIndex = ndInt32(m_triangles[i].m_w);
			indexList[duplicateIndex] = vertexCount;
		}
		--i;
		vertexCount++;
	}

	for (ndInt32 i = 0; i < vertexCount; ++i)
	{
		ndInt32 j = strideInFloats * i;
		m_triangles[i] = ndVector::m_zero;
		posit[j + 0] = ndReal(m_trianglesScratchBuffer[i].m_x);
		posit[j + 1] = ndReal(m_trianglesScratchBuffer[i].m_y);
		posit[j + 2] = ndReal(m_trianglesScratchBuffer[i].m_z);
	}

	// calculate normals
	for (ndInt32 i = 0; i < count; i += 3)
	{
		ndInt32 id0 = indexList[i + 0] * strideInFloats;
		ndInt32 id1 = indexList[i + 1] * strideInFloats;
		ndInt32 id2 = indexList[i + 2] * strideInFloats;

		const ndVector p0(posit[id0 + 0], posit[id0 + 1], posit[id0 + 2], ndFloat32(0.0f));
		const ndVector p1(posit[id1 + 0], posit[id1 + 1], posit[id1 + 2], ndFloat32(0.0f));
		const ndVector p2(posit[id2 + 0], posit[id2 + 1], posit[id2 + 2], ndFloat32(0.0f));
		const ndVector vec1(p1 - p0);
		const ndVector vec2(p2 - p0);

		const ndVector normal = vec1.CrossProduct(vec2);
		m_triangles[indexList[i + 0]] += normal;
		m_triangles[indexList[i + 1]] += normal;
		m_triangles[indexList[i + 2]] += normal;
	}

	// Normalize normals.
	for (ndInt32 i = 0; i < vertexCount; ++i)
	{
		ndVector normal(m_triangles[i] * m_triangles[i].InvMagSqrt());
		ndInt32 j = strideInFloats * i;
		normals[j + 0] = ndReal (normal.m_x);
		normals[j + 1] = ndReal (normal.m_y);
		normals[j + 2] = ndReal (normal.m_z);
	}

	return vertexCount;
}

void ndIsoSurface::ndImplementation::MakeTriangleList(ndIsoSurface* const me)
{
	D_TRACKTIME();
	ndArray<ndVector>& points = me->m_points;
	points.SetCount(m_triangles.GetCount());

	for (ndInt32 i = 0; i < ndInt32 (m_triangles.GetCount()); ++i)
	{
		points[i] = m_triangles[i] * m_gridSize;
	}
}

//void ndIsoSurface::ndImplementation::GenerateHighResIndexList(ndIsoSurface* const me)
void ndIsoSurface::ndImplementation::GenerateHighResIndexList(ndIsoSurface* const)
{
	D_TRACKTIME();
	ndAssert(0);
}

void ndIsoSurface::ndImplementation::CreateGrids()
{
	D_TRACKTIME();
	const ndGridHashSteps steps;
	m_hashGridMap.SetCount(m_hashGridMapScratchBuffer.GetCount() * 8);
	for (ndInt32 i = 0; i < m_hashGridMapScratchBuffer.GetCount(); ++i)
	{
		const ndGridHash hashKey(m_hashGridMapScratchBuffer[i]);
		for (ndInt32 j = 0; j < 8; ++j)
		{
			ndGridHash cell(hashKey);
			cell.m_x += steps.m_steps[j].m_x;
			cell.m_y += steps.m_steps[j].m_y;
			cell.m_z += steps.m_steps[j].m_z;
			cell.m_cellType = steps.m_cellType[j];
			m_hashGridMap[i * 8 + j] = cell;
		}
	}
}

void ndIsoSurface::ndImplementation::ClearBuffers()
{
	D_TRACKTIME();
	m_triangles.SetCount(0);
	m_hashGridMap.SetCount(0);
	m_trianglesScratchBuffer.SetCount(0);
	m_hashGridMapScratchBuffer.SetCount(0);
}

//void ndIsoSurface::ndImplementation::BuildHighResolutionMesh(ndIsoSurface* const me, const ndArray<ndVector>& points, ndFloat32 gridSize, ndCalculateIsoValue* const computeIsoValue)
void ndIsoSurface::ndImplementation::BuildHighResolutionMesh(ndIsoSurface* const, const ndArray<ndVector>&, ndFloat32, ndCalculateIsoValue* const)
{
	D_TRACKTIME();
	ndAssert(0);
	//CalculateAabb(points, gridSize);
	//RemoveDuplicates(points);
	//CreateGrids();
	//SortCellBuckects();
	//GenerateHighResIsoSurface(computeIsoValue);
	//GenerateLowResIndexList(me);
	//CalculateNormals(me);
	//ClearBuffers();
}

void ndIsoSurface::ndImplementation::BuildLowResolutionMesh(ndIsoSurface* const me, const ndArray<ndVector>& points, ndFloat32 gridSize)
{
	D_TRACKTIME();
	CalculateAabb(points, gridSize);
	RemoveDuplicates(points);
	CreateGrids();
	SortCellBuckects();
	GenerateLowResIsoSurface();
	MakeTriangleList(me);
	//GenerateLowResIndexList(me);
	//CalculateNormals(me);
	ClearBuffers();
}

ndIsoSurface::ndIsoSurface()
	:m_origin(ndVector::m_zero)
	,m_points(1024)
	,m_implement(new ndImplementation())
	,m_gridSize(ndFloat32(1.0f))
	,m_volumeSizeX(1)
	,m_volumeSizeY(1)
	,m_volumeSizeZ(1)
	,m_isLowRes(true)
{
}

ndIsoSurface::~ndIsoSurface()
{
	//GetImplementation().Clear();
	if (m_implement)
	{
		delete m_implement;
	}
}

void ndIsoSurface::GenerateMesh(const ndArray<ndVector>& pointCloud, ndFloat32 gridSize, ndCalculateIsoValue* const computeIsoValue)
{
	if (pointCloud.GetCount())
	{
		if (!computeIsoValue)
		{
			m_isLowRes = true;
			m_implement->BuildLowResolutionMesh(this, pointCloud, gridSize);
		}
		else
		{
			ndAssert(0);
			m_isLowRes = false;
			m_implement->BuildHighResolutionMesh(this, pointCloud, gridSize, computeIsoValue);
		}
		m_gridSize = gridSize;
		m_origin = m_implement->GetOrigin();
		m_volumeSizeX = m_implement->m_volumeSizeX;
		m_volumeSizeY = m_implement->m_volumeSizeY;
		m_volumeSizeZ = m_implement->m_volumeSizeZ;
	}
}

ndInt32 ndIsoSurface::GenerateListIndexList(ndInt32* const indexList, ndInt32 strideInFloats, ndReal* const posit, ndReal* const normals) const
{
	ndInt32 vertexCount = 0;
	if (m_isLowRes)
	{
		vertexCount = m_implement->GenerateLowResIndexList(this, indexList, strideInFloats, posit, normals);
	}
	else
	{
		ndAssert(0);
	}
	return vertexCount;
}